graphallshortestpaths

[dist]=graphallshortestpaths(G)

G为表示点间连接关系与权值的稀疏矩阵。 可由sparse(begin,end,weight)函数生成。 其中begin和end分别为起点与对应终点组成的矩阵，weight为对应边的权重。 dist为最小距离组成的矩阵。

graphconncomp

[S,C] = graphconncomp(G)

G为稀疏矩阵。 S为找到的连通分量的数量。 C为一个向量，表示每个节点属于哪个连通分量。

graphisdag

TF=graphisdag(G)

测试有向图是否含有圈，不含圈返回1，否则返回0

graphisomorphism

[Isomorphic, Map] = graphisomorphism(G1, G2) [Isomorphic, Map] = graphisomorphism(G1, G2,‘Directed’, DirectedValue)

G1，G2为稀疏矩阵。 若G1，G2为无向图则输入DirectedValue为false，计算时将忽略G1，G2的上三角矩阵，其值默认为true。 当二图同构时Isomorphic返回为1，并且map返回二图节点与节点的一对一映射；当二图不同构时，Isomorphic返回为0，map为空。

graphisspantree

TF = graphisspantree(G)

确定一个图是否是生成树，是返回1，否则返回0

graphmaxflow

[MaxFlow, FlowMatrix, Cut] = graphmaxflow(G, SNode, TNode) […] = graphmaxflow(G, SNode, TNode, …‘Capacity’, CapacityValue, …) […] = graphmaxflow(G, SNode, TNode, …‘Method’, MethodValue, …)

G为稀疏矩阵 SNode和TNode分别为起始，终止节点。 CapacityValue为一列向量，用于指定矩阵G中边的自定义容量，矩阵G中的每个非零值（边）必须输入一个容量。向量中自定义容量的顺序必须与矩阵G中非零值的顺序匹配，它以列方式遍历。 默认情况下，graphmaxflow从矩阵G中的非零输入中获取容量信息。 MethodValue为一字符向量或字符串，用于指定查找最小生成树的算法， （1）‘Edmonds’-使用Edmonds and Karp算法，基于标签算法的变体。 时间复杂度为O(N * E2)，其中N和E分别是节点数和边数。 （2）‘Goldberg’-默认算法。 使用Goldberg算法，该算法使用叫做preflow-push的通用方法。 时间复杂度为O(N2 *sqrt(E))，其中N和E分别是节点数和边数。

graphminspantree

[Tree, pred] = graphminspantree(G) [Tree, pred] = graphminspantree(G, R) [Tree, pred] = graphminspantree(…, ‘Method’, MethodValue, …) [Tree, pred] = graphminspantree(…, ‘Weights’, WeightsValue, …)

G为稀疏矩阵。 R为1到节点数之间的标量。 没有参数R时，找到连接无向图G中所有节点的边的无环子集，并且总权重被最小化。边的权重是N×N稀疏矩阵G的下三角矩阵中的所有非零项。输出树是由稀疏矩阵表示的生成树。输出pred是一个向量，其中包含最小生成树（MST）的前驱节点，其根节点用0表示。根节点默认为最大连通分量中的第一个节点。此计算需要额外调用graphconncomp函数。 存在参数R时，最小生成树的根节点为R。 MethodValue为一字符串 ‘Kruskal’-Kruskal算法，时间复杂度为O(E+X*log(N)）其中N和E分别是节点和边的数量。 ‘Prim’-默认算法，Prim算法，O(E*log(N))，其中N和E分别是节点和边的数量。 当图未连接时，Prim的算法仅返回包含R的树，而Kruskal的算法为每个分量返回MST。 WeightsValue是一列向量，矩阵G中的每个非零值（边）都有一个输入值。向量中自定义权重的顺序必须与矩阵G中的非零值的顺序相符（逐列遍历）。 默认情况下，graphminspantree从矩阵G中的非零输入获取权重信息。

graphshortestpath

[dist,path,pred] = graphshortestpath(G,S) [___] = graphshortestpath(G,S,D) [___] = graphshortestpath(___,Name,Value)

G为稀疏矩阵 S为起始节点 D为目标节点 dist包含从源节点到所有其他节点的距离。 path包含到每个节点的最短路径。 pred包含最短路径的前驱节点。

graphtopoorder

order = graphtopoorder(G)

返回索引向量，其中索引按拓扑顺序对节点进行排序。 按照拓扑顺序，当且仅当u按向量顺序出现在v之前，边才能存在于源节点u和目标节点v之间。 G是一个N×N的稀疏矩阵，代表有向无圈图（DAG）。 矩阵G中的非零项表示边的存在。

graphtraverse

[disc, pred, closed] = graphtraverse(G, S) […] = graphtraverse(G, S, …‘Depth’, DepthValue, …) […] = graphtraverse(G, S, …‘Directed’, DirectedValue, …) […] = graphtraverse(G, S, …‘Method’, MethodValue, …)

G为稀疏矩阵 S为起始节点 DepthValue为整数，表示图G中指定搜索深度的节点。 默认值为Inf（无穷大） DirectedValue若G为无向图则输入DirectedValue为false，计算时将忽略G的上三角矩阵，其值默认为true。 MethodValue为字符向量或字符串 （1）‘BFS’-广度优先搜索 （2）‘DFS’-默认算法，深度优先算法 disc是节点索引的向量，按发现顺序排列。 pred是生成的生成树的前驱节点索引（按节点索引的顺序列出）的向量。 closed是节点索引按其最近顺序的向量。